﻿// Prime Path POJ - 3126.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <set>
#include <cstring>
#include <math.h>



using namespace std;
//https://vjudge.csgrandeur.cn/problem/POJ-3126



/*

内阁部长们对安全局长的消息感到很不满，消息称他们都必须更改办公室的四位数房间号码。
— 这是安全问题，定期更改这些东西可以让敌人一头雾水。
— 但是，我选择1033这个数字是有充分理由的。我是首相，你知道！
— 我知道，所以你的新号码8179也是一个质数。你只需要在办公室门上的四位旧数字上贴上四位新数字。
— 不，事情并不那么简单。假设我把第一个数字改成8，那么数字就变成了8033，这不是一个质数！
— 我明白了，作为首相，你不能容忍在你的门上有一个非质数的数字，哪怕只有几秒钟。
— 对！所以我必须设计一个方案，通过质数路径从1033到8179，只改变一个数字，使得每个数字都是质数。

此时，一直在窃听的财政部长插话了。
— 请不要有不必要的开支！我碰巧知道一个数字的价格是一英镑。
— 嗯，在这种情况下，我需要一个计算机程序来最小化成本。你不知道一些非常便宜的软件专家吗？
— 其实我知道。你看，正在进行这个编程竞赛... 帮助首相找到任意两个给定的四位数质数之间的最便宜的质数路径！
当然，第一个数字必须是非零的。这是上面情况的一个解决方案。
1033
1733
3733
3739
3779
8779
8179
这个解决方案的成本是6英镑。请注意，在第2步中贴上的数字1不能在最后一步中重复使用 - 必须购买一个新的1。
输入
一行包含一个正整数：测试用例的数量（最多100个）。然后对于每个测试用例，一行包含两个用空格分隔的数字。
这两个数字都是四位数的质数（没有前导零）。
输出
每个案例输出一行，要么是一个说明最小成本的数字，要么是包含单词Impossible。

3
1033 8179
1373 8017
1033 1033

6
7
0

*/

int T;
set<int> ss;
set<int> vv;

void change(int n,int idx , queue<vector<int> >& q,int step) {
	int addnum = (int)pow(10,idx);
	int posnum = n % (addnum * 10)/ addnum;

	int next = n;
	for (int i = 9; i > posnum; i--) {
		next += addnum;
		if (ss.count(next) != 0 && vv.count(next) == 0) {
			vv.insert(next);
			//printf("%d step = %d\n", next, step + 1);
			q.push({ next,step + 1 });
		}
	}

	next = n;
	for (int i = 0; i < posnum; i++) {
		if (idx == 3 && i==0) continue;
		next -= addnum;
		if (ss.count(next) != 0 && vv.count(next) == 0) {
			vv.insert(next);
			//printf("%d step = %d\n", next, step + 1);
			q.push({ next,step + 1 });
		}
	}

	return;
}

void solve() {
	int a, b; cin >> a >> b;
	queue<vector<int> > q;
	vv.clear();

	q.push({ a,0 });
	vv.insert(a);
	while (!q.empty()) {
		int num = q.front()[0];
		int step = q.front()[1];
		q.pop();

		if (num == b) {
			cout << step << endl; return;
		}

		for (int i = 0; i < 4; i++) {
			change(num, i,q, step);
		}
	}

	cout << "Impossible" << endl;

	return;
}

bool st[10001];
int primes[10001];
void init() {
	 memset(primes,0,sizeof(primes)); int cnt = 0;
	 memset(st, 0, sizeof(st));

	for (int i = 2; i <= 10000; i++) {
		if (!st[i]) {
			primes[cnt++] = i;
			if(i>=1000&& i<=9999)ss.insert(i);
		}
		for (int j = 0; primes[j] <= 10000 / i; j++) {
			st[primes[j] * i] = true;
			if (i % primes[j] == 0) break;
		}
	}
}


int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("myout.txt", "w", stdout);


	cin >> T;
	init();
	while (T--) {
		solve();
	}

	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

 